import time
import matplotlib.pyplot as plt
from alg import Solution

plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示中文
plt.rcParams['axes.unicode_minus'] = False    # 正常显示负号

def read_cases():
    with open('cases.txt', 'r') as f:
        return [line.strip() for line in f.readlines()]

if __name__ == "__main__":
    lengths = list(range(10, 101, 10))
    cases = read_cases()
    dp_times = []
    dfs_times = []
    for n, s in zip(lengths, cases):
        sol = Solution()
        t1 = time.perf_counter()
        res1 = sol.numDecodings1(s)
        t2 = time.perf_counter()
        dp_times.append(t2 - t1)
        t1 = time.perf_counter()
        res2 = sol.numDecodings2(s)
        t2 = time.perf_counter()
        dfs_times.append(t2 - t1)
        # 正确性校验
        if res1 != res2:
            print(f"❌ 错误：长度{n}，DP结果={res1}，DFS结果={res2}，输入={s}")
        print(f"长度: {n}, DP: {dp_times[-1]:.6f}s, DFS: {dfs_times[-1]:.6f}s")
    # 画图
    plt.plot(lengths, dp_times, label="DP (O(n))")
    plt.plot(lengths, dfs_times, label="DFS (O(2^n))")
    plt.xlabel("输入长度")
    plt.ylabel("运行时间(s)")
    plt.title("两种算法复杂度对比（DP: O(n), DFS: O(2^n)）")
    plt.legend()
    plt.savefig("compare.png")
    plt.show() 